package org.xingole.leetcode.das.monostack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Problem：
 * 
 * Given string num representing a non-negative integer num, and an integer k, return 
 * the samllest possible integer after removing k digits from num.
 * 
 */
public class RemoveKDigits {

     /*
      * Approach : Greedy  with Stack
      *
      * We've got a hint while entertaining the idea of brute-force, that given two 
      * sequences of digit of the same length, it is the leftmost distinct digits that 
      * determine the superior of the two numbers, e.g. for A = 1axxx, B = 1bxxx, if the
      * digits a > b, then A > B.
      *
      * With this insight, the first intuition we got for our problem is that we should 
      * iterate from the left to right, when removing the digits. The more a digit to the
      * left-hand side, the more weight it carries.
      *
      * Now that we fix on the order of the iteration, it is critical to come up some 
      * criteria on how we eliminate digits, in order to obtain the minimum value.
      *
      * We could summarize the above scenario of removing a digit, as a rule below:
      *
      * Given a sequence of digits [D1D2D3...Dn], if the digit D2 is less than it left 
      * neighbor D1, then we should remove the left neighbor (D1) in order to obtain the
      * minimu result.
      *
      * One might notice that, there could be some cases where the condition to apply the 
      * rule does not hold for any of hte digits. 
      */
     public String removeKdigits(String num, int k) {
          // The element in the stack represents the smallest integer that can
          // be obtained by deleting no more than k numbers up to the current position
          // i.
          Deque<Character> stack = new LinkedList<>();

          int length = num.length();

          for ( int i = 0; i < length; i++ ) {
               char digit = num.charAt(i);
               while (!stack.isEmpty() && k > 0 && stack.peekLast() > digit ) {
                    stack.pollLast();
                    k--;
               }
               stack.offerLast(digit);
          }

          /* remove the remaining digits from the tail. */
          for ( int i = 0; i < k; i++ ) {
               stack.pollLast();
          }

          // build the final string, while removing the leading zeros.
          StringBuilder ret = new StringBuilder();
          boolean leadingZero = true;
          while (!stack.isEmpty()) {
               char digit = stack.pollFirst();
               if ( leadingZero && digit == '0' ) {
                    continue;
               }
               leadingZero = false;
               ret.append(digit);
          }
          return ret.length() == 0 ? "0" : ret.toString();
     }

}
